package nowcoder;
/**
 * 最近公共祖先
 * 链接：https://www.nowcoder.com/practice/70e00e490b454006976c1fdf47f155d9?tpId=8&&tqId=11017&rp=1&ru=/activity/oj&qru=/ta/cracking-the-coding-interview/question-ranking
 * 最近公共祖先
 *             1
 *      2              3
 *   4     5        6      7
 * 8  9  10  11  12  13  14  15
 */
public class Day11_1 {
    //先定义最近祖先
    private int lca = 1;
    public int getLCA(int a, int b) {
        findNode(1, a, b);
        return lca;
    }
    //检验以root为根节点的二叉树中是否有p或q
    private boolean findNode(int root, int a, int b) {
        //边界条件: 根节点比a和b小
        if(root < Math.max(a, b)){
            return false;
        }
        //检验根节点
        int cur = (root == a || root == b) ? 1 : 0;
        //检验左子树
        int left = findNode(root * 2, a, b) ? 1 : 0;
        //检验右子树
        int right = findNode(root * 2 + 1, a, b) ? 1 : 0;

        //当两个节点出现在根节点的左右两侧时，该根节点就是最近祖先
        if(cur + left + right == 2){
            lca = cur;
        }
        return cur + left + right > 0;
    }

    /******************* 方法二 **********************/
    public int getLCA2(int a, int b) {
        return getSameParent(a, b);
    }

    private int getSameParent(int a, int b) {
        if(a == b){
            return a;
        }else if(a > b){
            // 保证a < b
            a = a + b - (b = a);
        }
        // 给大的孩子b 找母亲
        b = b / 2;
        return getSameParent(a, b);
    }
}
